package leetcode.hot100;

@SuppressWarnings("all")
public class _34_在排序数组中查找元素的第一个和最后一个位置 {

    // 给定一个按照升序排列的整数数组 nums，和一个目标值 target
    // 找出给定目标值在数组中的开始位置和结束位置
    // 如果数组中不存在目标值 target，返回 [-1, -1]
    // 用时间复杂度为 O(log n) 的算法解决此问题

    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) return new int[]{-1, -1};
        // 先通过二分查找找到目标元素，再以该元素位置为中心点，向左右查找第一个和最后一个出现的位置
        int left = 0;
        int right = nums.length - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) >> 1;
            if (nums[mid] == target) {
                left = mid - 1;
                while (left >= 0 && nums[left] == target) {
                    left--;
                }
                right = mid + 1;
                while (right < nums.length && nums[right] == target) {
                    right++;
                }
                return new int[]{left + 1, right - 1};
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return new int[]{-1, -1};
    }
}
